package xoroperation;



/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-01-09
 * Time: 23:45
 */
//异或运算解决出现奇数次和偶数次的数的问题
public class EvenTimesOddTimes {
    //一个数出现奇数次，其余的数出现偶数次，找到这个数
    public static void printOddTimesNum1(int[] arr){
        int res=0;
        for(int i=0;i<arr.length;i++){
            //0^a=a
            //a^=a=0
            res^=arr[i];
        }
        System.out.println(res);
    }
    //有两个数出现了奇数次，其余的出现偶数次，找到并打印这两个数
    public static  void printOddTimesNum2(int[] arr){
        int xor=0;
        for(int i=0;i<arr.length;i++){
            //最终是两个出现奇数次异或的结果
            xor^=arr[i];
        }
        //关键是如何提取出两个出现奇数次的数
        //提取出二进制的最后一个1的数
        int rightOne=xor & (-xor);
        //让这个数异或二进制
        int onlyOne=0;
        for(int i=0;i<arr.length;i++){
            //让数组的元素与二进制最后一个1按位与，如果结果是1，那么就使用一个新的数异或上，最后的结果就是其中一个出现奇数次的数
            if((arr[i]&rightOne)!=0){
                onlyOne^=arr[i];
            }
        }
        //原来的异或结果再异或就是另一个数
        System.out.println(onlyOne + " " + (xor ^ onlyOne));
    }
}
